int modPowDFS(int a, int p, int mo) {
	// qiu a^p mod mo
	if (p == 0) {
		return 1 % mo;
	}
	int tmp = modPowDFS(a, p / 2, mo);
	if (p & 1) {
		return (long long)tmp * tmp * a % mo;
	} else {
		return (long long)tmp * tmp % mo;
	}
}

int modPowFor1(int a, int p, int mo) {
	// haishi qiu a^p mod mo
	int x = a, ans = 1;
	for (int i = 0; (1 << i) <= p; ++ i) {
		// x = a ^ (2^i)
		if (p & (1 << i)) {
			s = (long long)s * x % mo;
		}
		x = (long long)x * x % mo;
	}
}

int modPowFor2(int a, int p, int mo) {
	// yi ran haishi qiu a^p mod mo
	int s = 1; // zhe jiu shi da an 
	for (; p; p >>= 1) {
		if (p & 1) {
			s = (long long)s * a % mo;
		}
		a = (long long)a * a % mo;
	}
	return s;
}
